package william.array;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author ZhangShenao
 * @date 2024/1/11
 * @description <a href="https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array/description/">...</a>
 */
public class Leetcode448_找到所有数组中消失的数字 {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length == 0) {
            return Collections.emptyList();
        }

        //数组中的每个元素都在[1,n]区间内
        //首先遍历数组,将(nums[i]-1)下标处的元素取反,设置为负数
        for (int i = 0; i < nums.length; i++) {
            //这里取绝对值,因为可能存在避免重复元素,导致该位置已经被处理过了
            int idx = Math.abs(nums[i]) - 1;
            nums[idx] = -Math.abs(nums[idx]);
        }

        //再次遍历数组,如果发现某个元素仍未正数,则说明该下标+1的元素没有出现
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 0) {
                result.add(i + 1);
            }
        }

        //返回结果
        return result;
    }
}
